
public class TestDemo {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param number int整型 
     * @return int整型
     */
    public static int jumpFloorII (int number) {

        /**
         * 1）假定第一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1)；假定第一次跳的是2阶，那么剩下的是n-2个台阶，跳法是f(n-2)；假定第一次跳的是3阶，那么剩下的是n-3个台阶，跳法是f(n-3)......假定第一次跳的是n-1阶，那么剩下的是1个台阶，跳法是f(1)；
         * 假定第一次跳的是n阶，那么剩下的是0个台阶，跳法是1种；
         * （2）总跳法为: f(n) = 1+f(n-1) + f(n-2)+....+f(1)  （第一个1是跳n阶只有一种方法）
         *  (3）根据（2）可以得出有一阶的时候 f(1) = 1 ；有两阶的时候可以有
         *  f(2) =1+f(1)=2；有三阶的时候可以有 f(3) = 1+f(2)+f(1)=4...依次内推，有n阶时f(n)=2^(n-1)。
         */
        // 解法一: 找规律
        // return 1 << (number - 1);

        // 解法二: 递归
        if(number <= 0) {
            return 0;
        } else if(number == 1){
            return 1;
        } else {
            return 2 * jumpFloorII(number - 1);
        }
    }

    public static void main(String[] args) {
        System.out.println(jumpFloorII(5));
    }
}